﻿using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_88 : BaseProblem
    {

        public override object GetResult()
        {
            const int max = 12000;

            var _dct = new Dictionary<long, List<List<long>>>();
            MathLogic.GetPrimeList(max, true);

            var dct = new Dictionary<long, long>();

            var cur = 1;
            while (true)
            {
                cur++;
                var tmp = FormeLists(ref _dct, cur);
                foreach (var list in tmp)
                {
                    if (list.Count == 1) continue;
                    long sum = 0;
                    foreach (var l in list)
                    {
                        sum += l;
                        if (sum > cur) break;
                    }
                    if (sum > cur) continue;
                    var k = cur - sum + list.Count;
                    if (k > max) continue;
                    if (!dct.ContainsKey(k)) dct.Add(k, cur);
                    if (dct.Count >= max-1) break;
                }
                if (dct.Count >= max-1) break;

            }

            var hs = new HashSet<long>();
            long res = 0;
            foreach (var pair in dct)
            {
                if (hs.Contains(pair.Value)) continue;
                hs.Add(pair.Value);
                res += pair.Value;
            }

            return res;
        }

        private static List<List<long>> FormeLists(ref Dictionary<long, List<List<long>>> dct, long value)
        {
            if (dct.ContainsKey(value)) return dct[value];
            if (MathLogic.IsPrimeNumber(value, true)) return new List<List<long>>(){new List<long>(){value}};
            var facts = MathLogic.GetPrimeFactors(value);
            var res = new List<List<long>>();
            foreach (var fact in facts)
            {
                var tmp = value/fact.Key;
                var lst = FormeLists(ref dct, tmp);
                foreach (var list in lst)
                {
                    for (var i = 0; i <= list.Count; i++)
                    {
                        var qqq = new List<long>(list);
                        if (i < list.Count)
                        {
                            qqq[i] *= fact.Key;
                        }
                        else
                        {
                            qqq.Add(fact.Key);
                        }
                        var ex = false;
                        for (var j = 0; j < res.Count; j++)
                        {
                            if (!MathLogic.IsEqual(qqq, res[j])) continue;
                            ex = true;
                            break;
                        }
                        if (!ex)
                            res.Add(qqq);
                    }

                }

            }
            dct.Add(value, res);
            return res;
        }

        public override string Problem
        {
            get
            {
                return @"A natural number, N, that can be written as the sum and product of a given set of at least two natural numbers, {a1, a2, ... , ak} is called a product-sum number: N = a1 + a2 + ... + ak = a1  a2  ...  ak.

For example, 6 = 1 + 2 + 3 = 1  2  3.

For a given set of size, k, we shall call the smallest N with this property a minimal product-sum number. The minimal product-sum numbers for sets of size, k = 2, 3, 4, 5, and 6 are as follows.

k=2: 4 = 2  2 = 2 + 2
k=3: 6 = 1  2  3 = 1 + 2 + 3
k=4: 8 = 1  1  2  4 = 1 + 1 + 2 + 4
k=5: 8 = 1  1  2  2  2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1  1  1  1  2  6 = 1 + 1 + 1 + 1 + 2 + 6

Hence for 2k6, the sum of all the minimal product-sum numbers is 4+6+8+12 = 30; note that 8 is only counted once in the sum.

In fact, as the complete set of minimal product-sum numbers for 2k12 is {4, 6, 8, 12, 15, 16}, the sum is 61.

What is the sum of all the minimal product-sum numbers for 2k12000?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 7587457;
            }
        }

    }
}
